/*
 * @lc app=leetcode.cn id=740 lang=java
 *
 * [740] 删除并获得点数
 */

// @lc code=start
class Solution {
    public int deleteAndEarn(int[] nums) {

        if(nums == null || nums.length == 0) {
            return 0;
        } else if(nums.length == 1) {
            return nums[0];
        }


        int maxVal = 0;
        for(int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        int[] cnt = new int[maxVal+1];
        for(int num : nums) {
            cnt[num]++;
        }

        int[] dp = new int[maxVal+1];
        dp[1] = cnt[1] * 1;

        for(int i = 2; i <= maxVal; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + cnt[i] * i);
        }

        return dp[maxVal];
    }
}
// @lc code=end

